#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

class BinaryTree
{
public:
    using ElementType = int;

    BinaryTree();  //默认构造函数
    ~BinaryTree();  //析构函数

    void Insert(const ElementType & element);  //插入元素
    void Remove(const ElementType & element);  //删除元素
    ElementType* Find(const ElementType & element);  //查找元素
    void show();  //展示树
    
private:
    struct TreeNode
    {
        TreeNode(const ElementType & element):data(element)
        {
            left = right = parent = nullptr;
        }
        ElementType data;  //数据域
        TreeNode *left;  //左孩子指针
        TreeNode *right;  //右孩子指针
        TreeNode *parent;  //父节点指针
    };
    TreeNode* InsertNode(TreeNode *node, const ElementType & element);  //插入节点
    void PrevTravel(TreeNode *node);  //前序遍历
    void MidTravel(TreeNode *node);  //中序遍历
    void PostTravel(TreeNode *node);  //后序遍历
    void FreeNode(TreeNode *node);  //释放节点
    TreeNode* RemoveNode(TreeNode *node, const ElementType & element);  //删除节点
    TreeNode* GetMinNode(TreeNode *node);  //获取最小节点
    ElementType* FindNode(TreeNode *node,const ElementType & element);  //查找节点
    TreeNode* RotateRight(TreeNode *root);  //右旋
    TreeNode* RotateLeft(TreeNode *root);  //左旋
    TreeNode* RotateLeftRight(TreeNode *root);  //左右旋
    TreeNode* RotateRightLeft(TreeNode *root);  //右左旋
    int GetNodeHeight(TreeNode *node);  //获取节点高度
    int LRDevition(TreeNode *node);  //获取左右子树高度差
    TreeNode *root;  //根节点指针

};







#endif
